#include "filesys/inode.h"
#include <list.h>
#include <debug.h>
#include <round.h>
#include <string.h>
#include "filesys/filesys.h"
#include "filesys/free-map.h"
#include "threads/malloc.h"
#include "filesys/cache.h"

/* Identifies an inode. */
#define INODE_MAGIC 0x494e4f44
#define SECTOR_INODE_SIZE 140
#define SECTOR_ERR_IDX 32767 
static char zeros[DISK_SECTOR_SIZE];

/* On-disk inode.
	 Must be exactly DISK_SECTOR_SIZE bytes long. */
struct inode_disk
{
	off_t length;                       /* File size in bytes. */
	int16_t sector_idx[SECTOR_INODE_SIZE];
	int32_t occupied;
	unsigned magic;                     /* Magic number. */
	uint32_t unused[53];               /* Not used. */
	bool is_dir;
	int parent_dir_idx;
};


/* Returns the number of sectors to allocate for an inode SIZE
	 bytes long. */
	static inline size_t
bytes_to_sectors (off_t size)
{
	return DIV_ROUND_UP (size, DISK_SECTOR_SIZE);
}

static inline size_t
bytes_to_inodes (off_t size)
{
	return DIV_ROUND_UP (bytes_to_sectors(size), SECTOR_INODE_SIZE);
}
/* In-memory inode. */
struct inode 
{
	struct list_elem elem;              /* Element in inode list. */
	disk_sector_t sector;               /* Sector number of disk location. */
	int open_cnt;                       /* Number of openers. */
	bool removed;                       /* True if deleted, false otherwise. */
	int deny_write_cnt;                 /* 0: writes ok, >0: deny writes. */
	struct inode_disk data;             /* Inode content. */
};

bool get_is_dir(struct inode *inode)
{
	if(inode == NULL)
		return false;
	return inode->data.is_dir;
}

void set_is_dir(struct inode *inode)
{
	if(inode == NULL)
		return;
	inode->data.is_dir = true;
}

int get_parent_dir_idx(struct inode *inode)
{
	if(inode == NULL)
		return -1;
	return inode->data.parent_dir_idx;
}

void set_parent_dir_idx(struct inode *inode, int idx)
{
	if(inode == NULL)
		return;
	inode->data.parent_dir_idx = idx;
}

static void init_inode_disk( struct inode_disk *id, int length )
{
	int i;
	id->occupied = -1;
	for ( i = 0 ; i < length ; ++i)
		id->sector_idx[i] = SECTOR_ERR_IDX;
}

void clear_inode_disk( struct inode_disk *id)
{
	size_t i,j;
	for ( i = 0; i < bytes_to_inodes(id->length) ; ++i) {
		if ( id->sector_idx[ i ] == SECTOR_ERR_IDX) 
			break;
		struct inode *temp = inode_open (id->sector_idx[ i ]);
		for ( j = 0; j < SECTOR_INODE_SIZE; j++) {
			if( temp->data.sector_idx[j] == SECTOR_ERR_IDX)
				break;
			cache_remove(temp->data.sector_idx[j]);
			free_map_release (temp->data.sector_idx[j],1);
		}
		inode_close (temp);
		cache_remove(id->sector_idx[i]);
		free_map_release (id->sector_idx[ i ], 1);
	}

}
/* Returns the disk sector that contains byte offset POS within
	 INODE.
	 Returns -1 if INODE does not contain data for a byte at offset
	 POS. */
	static disk_sector_t
byte_to_sector (const struct inode *inode, off_t pos) 
{
	ASSERT (inode != NULL);

#if 0
	if (pos < inode->data.length)
		return inode->data.start + pos / DISK_SECTOR_SIZE;
	else
		return -1;
#else
	if ( pos >= inode->data.length){
		return SECTOR_ERR_IDX;
	}
	int nomalized = (pos/DISK_SECTOR_SIZE);
	int idx1 = inode->data.sector_idx[ nomalized / SECTOR_INODE_SIZE];
	struct inode *child = inode_open(idx1);
	disk_sector_t ret = child->data.sector_idx[nomalized % SECTOR_INODE_SIZE];
	inode_close(child);

	return ret;
#endif
}

/* List of open inodes, so that opening a single inode twice
	 returns the same `struct inode'. */
static struct list open_inodes;

/* Initializes the inode module. */
	void
inode_init (void) 
{
	list_init (&open_inodes);
	sema_init( &growth_sema, 1);
}

/* Initializes an inode with LENGTH bytes of data and
	 writes the new inode to sector SECTOR on the file system
	 disk.
	 Returns true if successful.
	 Returns false if memory or disk allocation fails. */
	bool
inode_create (disk_sector_t sector, off_t length)
{
	struct inode_disk *disk_inode = NULL;
	bool success = true;

	ASSERT (length >= 0);

	/* If this assertion fails, the inode structure is not exactly
		 one sector in size, and you should fix that. */
	ASSERT (sizeof *disk_inode == DISK_SECTOR_SIZE);

#if 0
	disk_inode = calloc (1, sizeof *disk_inode);
	if (disk_inode != NULL)
	{
		size_t sectors = bytes_to_sectors (length);
		disk_inode->length = length;
		disk_inode->magic = INODE_MAGIC;
		disk_inode->is_dir = false;
		disk_inode->parent_dir_idx = ROOT_DIR_SECTOR;
		if (free_map_allocate (sectors, &disk_inode->start))
		{
			disk_write (filesys_disk, sector, disk_inode);
			if (sectors > 0) 
			{
				size_t i;

				for (i = 0; i < sectors; i++) 
					disk_write (filesys_disk, disk_inode->start + i, zeros); 
			}
			success = true; 
		} 
		free (disk_inode);
	}
	return success;
#else
	size_t sectors = bytes_to_sectors (length); 
	size_t n_i = bytes_to_inodes(length);
	size_t i, j;
	disk_inode = calloc (1, sizeof *disk_inode);
	if (disk_inode != NULL)
	{
		disk_inode->length = length;
		disk_inode->magic = INODE_MAGIC;
		disk_inode->is_dir = false;
		disk_inode->occupied = -1;
		disk_inode->parent_dir_idx = ROOT_DIR_SECTOR;
		//initialize

		init_inode_disk( disk_inode , SECTOR_INODE_SIZE);
		for ( i = 0; i < n_i; ++i) {

			disk_sector_t sidx;

			if (free_map_allocate (1, &sidx)) {
				disk_inode->sector_idx[ i ] = sidx;

				//indirect idx	
				size_t n_j =  ( sectors  < (i+1)*SECTOR_INODE_SIZE) ? sectors % SECTOR_INODE_SIZE : SECTOR_INODE_SIZE;
				struct inode_disk indirect;
				init_inode_disk( &indirect , n_j);

				for ( j = 0; j < n_j ; j++) {
					if (free_map_allocate (1, &sidx)) {
						indirect.sector_idx[j] = sidx;
						cache_write( indirect.sector_idx[j], 0, DISK_SECTOR_SIZE, zeros);

					} else {
						success = false;
						break;
					}
				} 
				if(success) 
					cache_write( disk_inode->sector_idx[i],0,DISK_SECTOR_SIZE,&indirect);
				else 
					break;
			} else {
				success = false;
				break;
			}
		}
		if(success)
			cache_write( sector,0,DISK_SECTOR_SIZE,disk_inode);
	}

	if ( !success) {
		clear_inode_disk( disk_inode);
	}

	free (disk_inode);
	return success;

#endif
}


/* Reads an inode from SECTOR
	 and returns a `struct inode' that contains it.
	 Returns a null pointer if memory allocation fails. */
	struct inode *
inode_open (disk_sector_t sector) 
{
	struct list_elem *e;
	struct inode *inode;

	/* Check whether this inode is already open. */
	for (e = list_begin (&open_inodes); e != list_end (&open_inodes);
			e = list_next (e)) 
	{
		inode = list_entry (e, struct inode, elem);
		if (inode->sector == sector) 
		{
			inode_reopen (inode);
			return inode; 
		}
	}

	/* Allocate memory. */
	inode = malloc (sizeof *inode);
	if (inode == NULL)
		return NULL;

	/* Initialize. */
	list_push_front (&open_inodes, &inode->elem);
	inode->sector = sector;
	inode->open_cnt = 1;
	inode->deny_write_cnt = 0;
	inode->removed = false;
	cache_read( inode->sector, 0, DISK_SECTOR_SIZE, &inode->data);
	return inode;
}

/* Reopens and returns INODE. */
struct inode *
inode_reopen (struct inode *inode)
{
	if (inode != NULL)
		inode->open_cnt++;
	return inode;
}

/* Returns INODE's inode number. */
disk_sector_t
inode_get_inumber (const struct inode *inode)
{
	return inode->sector;
}

/* Closes INODE and writes it to disk.
	 If this was the last reference to INODE, frees its memory.
	 If INODE was also a removed inode, frees its blocks. */
void
inode_close (struct inode *inode) 
{
	/* Ignore null pointer. */
	if (inode == NULL)
		return;

	/* Release resources if this was the last opener. */
	if (--inode->open_cnt == 0)
	{
		/* Remove from inode list and release lock. */
		list_remove (&inode->elem);

		/* Deallocate blocks if removed. */
		if (inode->removed) 
		{
			clear_inode_disk( &inode->data );
			free_map_release (inode->sector, 1);
			cache_remove(inode->sector);
		}
		else
		{
			cache_write( inode->sector, 0, DISK_SECTOR_SIZE, &inode->data);
		}

		free (inode); 
	}
}

/* Marks INODE to be deleted when it is closed by the last caller who
	 has it open. */
	void
inode_remove (struct inode *inode) 
{
	ASSERT (inode != NULL);
	inode->removed = true;
}

/* Reads SIZE bytes from INODE into BUFFER, starting at position OFFSET.
	 Returns the number of bytes actually read, which may be less
	 than SIZE if an error occurs or end of file is reached. */
	off_t
inode_read_at (struct inode *inode, void *buffer_, off_t size, off_t offset) 
{
	uint8_t *buffer = buffer_;
	off_t bytes_read = 0;

	while (size > 0) 
	{
		/* Disk sector to read, starting byte offset within sector. */
		disk_sector_t sector_idx = byte_to_sector (inode, offset);
		int sector_ofs = offset % DISK_SECTOR_SIZE;

		/* Bytes left in inode, bytes left in sector, lesser of the two. */
		off_t inode_left = inode_length (inode) - offset;
		int sector_left = DISK_SECTOR_SIZE - sector_ofs;
		int min_left = inode_left < sector_left ? inode_left : sector_left;

		/* Number of bytes to actually copy out of this sector. */
		int chunk_size = size < min_left ? size : min_left;
		if (chunk_size <= 0)
			break;

		cache_read(sector_idx, sector_ofs, chunk_size, buffer + bytes_read);

		/* Advance. */
		size -= chunk_size;
		offset += chunk_size;
		bytes_read += chunk_size;
	}

	return bytes_read;
}

off_t file_growth(struct inode_disk *id , off_t sz)
{
	disk_sector_t sec_no;

	int i, j;
// divide length/ SECTOR_SIZE
	// indirect 
	// find index of 
	int i_n = id->length / DISK_SECTOR_SIZE;
	int new_n = sz/DISK_SECTOR_SIZE;
	
	bool first = true;
	for ( i = (i_n + 1) / SECTOR_INODE_SIZE; i <= (new_n) / SECTOR_INODE_SIZE; i++) {
		struct inode *inode2 = NULL;

		if ( id->sector_idx[ i ] == SECTOR_ERR_IDX) 
		{
			// add more indirect
			if ( free_map_allocate (1, &sec_no)) 
			{
				id->sector_idx[ i ] = sec_no;
				inode2 = inode_open (id->sector_idx[ i ]);
				init_inode_disk ( &inode2->data, SECTOR_INODE_SIZE);
			} 
			else 
				return 0;
		} 
		else 
		{
			// use already exist indirect
			inode2 = inode_open (id->sector_idx[ i ]);
		}

		//add child node
		for ( j = ( id->length != 0 && first ) ? (i_n + 1) % SECTOR_INODE_SIZE : 0; 
					j <=( ( i == (new_n)/ SECTOR_INODE_SIZE ) ? (new_n) % SECTOR_INODE_SIZE : SECTOR_INODE_SIZE-1 );
					++j) 
		{
			if ( free_map_allocate (1, &sec_no)) 
			{
				inode2->data.sector_idx[ j ] = sec_no;
				cache_write( inode2->data.sector_idx[ j ] , 0, DISK_SECTOR_SIZE, zeros);
			} 
			else 
				return 0;
		}
		inode_close (inode2);
		first = false;
	}
	// change length of inode
	id->length = sz;
	return 1;
}
/* Writes SIZE bytes from BUFFER into INODE, starting at OFFSET.
	 Returns the number of bytes actually written, which may be
	 less than SIZE if end of file is reached or an error occurs.
	 (Normally a write at end of file would extend the inode, but
	 growth is not yet implemented.) */
	off_t
inode_write_at (struct inode *inode, const void *buffer_, off_t size,
		off_t offset) 
{
	const uint8_t *buffer = buffer_;
	off_t bytes_written = 0;

	if (inode->deny_write_cnt)
		return 0;

	off_t sz_off = size+offset;	

	if( inode->data.length < sz_off){
		sema_down( &growth_sema );
	
		//file growth	!!!
		if( inode->data.length < sz_off )
		{
			if ( file_growth(&inode->data, sz_off) ){
				cache_write( inode->sector, 0, DISK_SECTOR_SIZE, &inode->data);
				sema_up( &growth_sema );
			}
			else{
				sema_up( &growth_sema );
				return 0;
			}
		}
		else{
			sema_up( &growth_sema );
		}
	}

	while (size > 0) 
	{
		/* Sector to write, starting byte offset within sector. */
		disk_sector_t sector_idx = byte_to_sector (inode, offset);
		int sector_ofs = offset % DISK_SECTOR_SIZE;

		/* Bytes left in inode, bytes left in sector, lesser of the two. */
		off_t inode_left = inode_length (inode) - offset;
		int sector_left = DISK_SECTOR_SIZE - sector_ofs;
		int min_left = inode_left < sector_left ? inode_left : sector_left;

		/* Number of bytes to actually write into this sector. */
		int chunk_size = size < min_left ? size : min_left;
		if (chunk_size <= 0)
			break;

		cache_write(sector_idx, sector_ofs, chunk_size, (void*)(buffer + bytes_written));

		/* Advance. */
		size -= chunk_size;
		offset += chunk_size;
		bytes_written += chunk_size;
	}

	return bytes_written;
}

/* Disables writes to INODE.
	 May be called at most once per inode opener. */
	void
inode_deny_write (struct inode *inode) 
{
	inode->deny_write_cnt++;
	ASSERT (inode->deny_write_cnt <= inode->open_cnt);
}

/* Re-enables writes to INODE.
	 Must be called once by each inode opener who has called
	 inode_deny_write() on the inode, before closing the inode. */
	void
inode_allow_write (struct inode *inode) 
{
	ASSERT (inode->deny_write_cnt > 0);
	ASSERT (inode->deny_write_cnt <= inode->open_cnt);
	inode->deny_write_cnt--;
}

/* Returns the length, in bytes, of INODE's data. */
	off_t
inode_length (const struct inode *inode)
{
	return inode->data.length;
}

